// st表
// https://www.luogu.com.cn/problem/P3865
int n, m;
int a[maxn];
int f[maxn][max_size]; // f[i][j] 从 i 开始，长度为 2 ^ j 的区间信息
int lg2[maxn];
inline int p2(int k) { return 1 << k; }

void init() {
    lg2[0] = -1;
    rf(i, n) lg2[i] = lg2[i / 2] + 1, f[i][0] = a[i];

    for (int j = 1; j <= 20; ++j)
        for (int i = 1; i + p2(j) - 1 <= n; ++i)
            f[i][j] = max(f[i][j - 1], f[i + p2(j - 1)][j - 1]);
}

int ask(int l, int r) {
    int k = lg2[r - l + 1];
    return max(f[l][k], f[r - p2(k) + 1][k]);
}
